Chessboard [B]

Memory limit: 128 MB

On an extremely large chess board many chessmen were located¹ - all of them of the same colour. We say that a given chessman can capture specified position on the chess board, if the chessman can move to that position, particularly:

• there is no chessman standing on destination position,
• there are no chessmen on the way from the initial position to the destination (in case of a queen, a rook and a bishop).

Task

Write a program which:

• reads a description of the chessboard from the standard input,
• for each chessman determines the number of positions being captured by that chessman,
• writes the result to the standard output.

Input

In the first line of the input there are two integers and (, ), separated with a single space and representing the number of chessmen located on the square chessboard and its dimension . Each of the following lines is of the format " ", where is a letter representing:

• G - bishop,
• H - queen,
• K - king,
• S - knight,
• W - rook,

Output

The output should consist of lines. 'th line should contain one integer, representing the number of positions being captured by 'th chessman from the input.

Example

For the input data:

6 5
K 5 5
G 4 1
W 1 3
K 2 3
H 2 2
S 3 3

the correct result is:

3
2
4
5
7
7

The image above represents the chessboard from the sample input. Lines of different style represent positions being captured by chessmen. The possible destinations of the knight are represented by big dots.

Task author: Jakub Radoszewski.